package q174_calculateMinimumHP;

public class Solution {
    /*
    此题的关键要求是 到达每个格子的时候血量都要大于0 也就是至少为1
    可以直接通过从右下向左上动态规划的方式来解决该问题 并且可以复用本题的矩阵 减少空间复杂
    首先对于终点 要求到达终点至少要有一滴血 并且到达任何一个格子都要扣除对应的血量 所以终点的血量也要被计入
    因此初始时终点血量应该设计为Math.max(1, 1 - dungeon[m][n]);也就是如果终点是一个正数 那么我们只需要有一滴血就能够进入终点
    否则就需要计算1 - dungeon[m][n]才能进入终点
    然后开始动态规划
    需要注意的是dp[i][j] 代表的是 从i j位置到达终点所需的最低血量
    所以每次我们动规之后原来的格子就不再代表扣除的血量值了 而代表需要的血量
    所以 当我们向左上递归时 可以分别从右侧和下侧的格子来推断需要的血量 自然应该选择一个之前推算的需要 更少血量 就能够到达终点的格子
    来计算当前格子到达终点需要的血量 也就是dungeon[i][j] = Math.max(1, Math.min(dungeon[i + 1][j], dungeon[i][j + 1]) - dungeon[i][j]);
     */
    public int calculateMinimumHP(int[][] dungeon) {
        int m = dungeon.length - 1, n = dungeon[0].length - 1;
        dungeon[m][n] = Math.max(1, 1 - dungeon[m][n]);
        for (int i = m; i >= 0; --i) {
            for (int j = n; j >= 0; --j) {
                if (i < m && j < n) {
                    dungeon[i][j] = Math.max(1, Math.min(dungeon[i + 1][j], dungeon[i][j + 1]) - dungeon[i][j]);
                } else if (i < m) {
                    dungeon[i][j] = Math.max(1, dungeon[i + 1][j] - dungeon[i][j]);
                } else if (j < n) {
                    dungeon[i][j] = Math.max(1, dungeon[i][j + 1] - dungeon[i][j]);
                }
            }
        }
        return dungeon[0][0];
    }
}
